Лемма о раскраске блоков

Хроматическое число графа равно максимуму хроматических чисел его блоков.

Достаточно доказать лемму для связного графа $G$. Пусть $B(G)$ — дерево блоков $G$. Любая точка сочленения принадлежит по крайней мере двум блокам, следовательно, листья $B(G)$ — это блоки (назовём их концевыми блоками). Проведём индукцию по числу $k$ блоков графа $G$. **База индукции:** $k = 1$ — очевидно. **Шаг индукции:** Пусть лемма верна для графов с $\le k$ блоками, а $G$ имеет $k+1$ блок. Пусть $B$ — концевой блок $G$, а $G'$ — объединение всех остальных блоков. Тогда графы $B$ и $G'$ имеют ровно одну общую вершину $v$, которая является точкой сочленения. Пусть $r$ — максимум хроматических чисел блоков графа $G$, тогда очевидно, что $\chi(G) \ge r$. Граф $G'$ имеет $k$ блоков, следовательно, по предположению индукции $\chi(G') \le r$. Зафиксируем произвольные оптимальные раскраски графов $B$ и $G'$ и рассмотрим два случая: 1. Вершина $v$ в графах $B$ и $G'$ раскрашена одинаково. В этом случае мы получили правильную раскраску графа $G$ в $\max\{\chi(B), \chi(G')\} = r$ цветов. 2. Вершина $v$ в графе $B$ раскрашена в $i$-й цвет, а в графе $G'$ — в $j$-й цвет, где $i \neq j$. Тогда заменим раскраску $f$ графа $B$ раскраской $f \circ \phi$, где $\phi\mathpunct{:}~ \{1, \dots, r\} \to \{1, \dots, r\}$ — перестановка, такая что $\phi(i) = j$ и $\phi(j) = i$. В результате мы получили правильную раскраску $B$, которая сводит задачу к случаю 1. $\square$